#ifndef TACORES_FLOYDWARSHALL_H
#define TACORES_FLOYDWARSHALL_H

using namespace std;

#include "Graph.h"
#include <vector>
#include <limits>

// O(V^3)
class FloydWarshall
{
public:
	FloydWarshall(Graph& g)
		: g (g)
	{
	}

	void allPairsShortest()
	{
		initialize();

		int size = g.numVertices();
		for(int t = 0; t < size; ++t)
		{
			for(int u = 0; u < size; ++u)
			{
				for(int v = 0; v < size; ++v)
				{
					int newLen = dist[u][t] + dist[t][v];
					if(newLen < dist[u][v])
					{
						dist[u][v] = newLen;
						pred[u][v] = pred[t][v];
					}
				}
			}
		}
	}
	vector<vector<int> > getPredecessor() { return pred; }
	vector<vector<int> > getDistance() { return dist; }

private:
	void initialize()
	{
		int size = g.numVertices();
		dist.resize(size);
		pred.resize(size);
		for(int u = 0; u < size; ++u)
		{
			dist[u].assign(size, numeric_limits<int>::max());
			pred[u].assign(size, -1);
			dist[u][u] = 0;

			VertexList::const_iterator end = g.end(u);
			for(VertexList::const_iterator it = g.begin(u); it != end; ++it)
			{
				int v = it->first;
				dist[u][v] = g.edgeWeight(u,v);
				pred[u][v] = u;
			}
		}
	}

	Graph& g;
	vector<vector<int> > dist;
	vector<vector<int> > pred;
};
typedef FloydWarshall FLWAR;

#endif

